/*
 * Copyright 北京航空航天大学 @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.stack;

import java.util.Stack;

/**
 * <p>
 * 计算逆波兰形式的表达式 有效操作符为四则运算 ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9 ["4", "13", "5", "/",
 * "+"]-> (4 + (13 / 5)) -> 6
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com 2015年5月24日
 */
public class EvaluateReversePolishNotation {

    public int evalRPN(String[] tokens) {
        int n = tokens.length;
        if (n == 0) {
            return 0;
        }
        int result = 0;
        boolean firstSign = true;
        // 数字 直接压栈，运算符第一个操作数为栈顶，第二个操作符为中间结果，计算此运算式的结果作为新的中间结果
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i < n; i++) {
            // 区别符号和数字
            if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
                if (firstSign) {
                    result = stack.pop();
                    firstSign = false;
                }
                int first = stack.pop();
                switch (tokens[i]) {
                    case "+":
                        result = first + result;
                        break;
                    case "-":
                        result = first - result;
                        break;
                    case "*":
                        result = first * result;
                        break;
                    case "/":
                        result = first / result;
                        break;
                    default:
                        break;
                }
            } else {// 压栈
                stack.push(Integer.valueOf(tokens[i]));
            }
        }
        return result;
    }
    public static void main(String[] args) {
        String tokens[] = {"2", "1", "+", "3", "*"};
        System.out.println(new EvaluateReversePolishNotation().evalRPN(tokens));
        }
}
